// 解题思路：
// 找递增三元组
// 遍历数组，看看当前元素是否可以拼接在前面的元素的后面，如果可以能拼接，且长度达到 3, 就返回 true
// 和前面的元素对比，可以使用贪心策略优化
// dp[i] 表示长度为 i 的递增子序列的最小元素
// 如果当前元素大于前面最大的元素，或者是第一个元素（前面还没有元素），就把 dp[++pos] = nums[i]
// 如果不大于，就遍历以下前面所有的元素，小于哪个元素，就替换哪个元素，即 if(nums[i] < do[j]) dp[j] = nums[i];

public class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        int[] dp = new int[4];
        int pos = 0;

        for(int i = 0; i < n; i++){
            if(pos == 0 || nums[i] > dp[pos]){
                dp[++pos] = nums[i];
                if(pos == 3) return true;
            }else{
                for(int j = 1; j <= pos; j++){
                    if(nums[i] <= dp[j]){
                        dp[j] = nums[i];
                        break;
                    }
                }
            }
        }
        return false;
    }
}
